import kotlinx.cinterop.*
import kotlin.native.concurrent.*
import platform.posix.*
import kotlin.system.getTimeNanos

private data class TaskParams(
    val taskId: Int,
    val chunkSize: Int,
    val n: Int,
    val fact: IntArray,
    val totalPerms: Int
)

private data class TaskResult(
    val maxFlips: Int,
    val chkSum: Int
)

// 纯Kotlin实现的浮点数格式化（替代String.format）
private fun formatDouble(value: Double, decimalPlaces: Int): String {
    val multiplier = 10.0.pow(decimalPlaces)
    val rounded = kotlin.math.round(value * multiplier) / multiplier
    return if (decimalPlaces == 0) {
        rounded.toInt().toString()
    } else {
        val parts = rounded.toString().split('.')
        val integerPart = parts[0]
        val decimalPart = if (parts.size > 1) parts[1] else "0"
        if (decimalPart.length >= decimalPlaces) {
            "$integerPart.${decimalPart.substring(0, decimalPlaces)}"
        } else {
            "$integerPart.${decimalPart.padEnd(decimalPlaces, '0')}"
        }
    }
}

fun main(args: Array<String>) {
    val n = if (args.isNotEmpty()) args[0].toIntOrNull() ?: 12 else 12
    if (n < 0 || n > 12) {
        println("-1")
        println("Pfannkuchen($n) = -1")
        return
    }
    if (n <= 1) {
        println("0")
        println("Pfannkuchen($n) = 0")
        return
    }

    for (i in 1..24) {
        val startTime = getTimeNanos()
        val (chkSum, maxFlips) = computeFannkuch(n)
        val endTime = getTimeNanos()

        println(chkSum)
        println("Pfannkuchen($n) = $maxFlips")

        // 使用纯Kotlin格式化函数
        val duration = (endTime - startTime).toDouble() / 1_000_000_000.0
        val formattedDuration = formatDouble(duration, 3)
        println("duration: $formattedDuration")
    }
}

private fun computeFannkuch(n: Int): Pair<Int, Int> {
    val fact = IntArray(n + 1).apply {
        this[0] = 1
        for (i in 1..n) this[i] = this[i - 1] * i
    }.freeze()
    val totalPerms = fact[n]

    val nChunks = 150
    val chunkSize = (totalPerms + nChunks - 1) / nChunks
    val nTasks = (totalPerms + chunkSize - 1) / chunkSize

    val tasks = List(nTasks) { taskId ->
        TaskParams(
            taskId = taskId,
            chunkSize = chunkSize,
            n = n,
            fact = fact,
            totalPerms = totalPerms
        ).freeze()
    }

    val nThreads = try {
        sysconf(_SC_NPROCESSORS_ONLN).toInt().coerceAtLeast(1)
    } catch (e: Exception) {
        4
    }
    val workers = List(nThreads) { Worker.start() }
    val futures = mutableListOf<Future<TaskResult>>()

    tasks.forEach { task ->
        val workerIndex = (task.taskId % nThreads).toInt()
        futures.add(
            workers[workerIndex].execute(
                mode = TransferMode.SAFE,
                producer = { task },
                job = ::processTask
            )
        )
    }

    val results = futures.map { it.result }
    workers.forEach { it.requestTermination() }

    return results.sumOf { it.chkSum } to results.maxOf { it.maxFlips }
}

private fun processTask(params: TaskParams): TaskResult {
    val (taskId, chunkSize, n, fact, totalPerms) = params
    val idxMin = taskId * chunkSize
    val idxMax = minOf(totalPerms, idxMin + chunkSize)

    val p = IntArray(n)
    val pp = IntArray(n)
    val count = IntArray(n)

    firstPermutation(idxMin, n, fact, p, pp, count)

    var maxFlips = 1
    var chkSum = 0

    for (i in idxMin until idxMax) {
        if (p[0] != 0) {
            val flips = countFlips(n, p, pp)
            maxFlips = maxOf(maxFlips, flips)
            chkSum += if (i % 2 == 0) flips else -flips
        }
        if (i + 1 < idxMax) {
            nextPermutation(n, p, count)
        }
    }

    return TaskResult(maxFlips, chkSum)
}

private fun firstPermutation(
    idx: Int,
    n: Int,
    fact: IntArray,
    p: IntArray,
    pp: IntArray,
    count: IntArray
) {
    for (i in 0 until n) p[i] = i
    var currentIdx = idx

    for (i in (n - 1) downTo 1) {
        val d = currentIdx / fact[i]
        count[i] = d
        currentIdx %= fact[i]

        for (j in 0..i) pp[j] = p[j]
        for (j in 0..i) {
            p[j] = if (j + d <= i) pp[j + d] else pp[j + d - i - 1]
        }
    }
}

private fun nextPermutation(n: Int, p: IntArray, count: IntArray) {
    val first = p[1]
    p[1] = p[0]
    p[0] = first

    var i = 1
    while (++count[i] > i) {
        count[i++] = 0
        p[0] = p[1]
        val next = p[0]
        for (j in 1 until i) p[j] = p[j + 1]
        p[i] = first
    }
}

private fun countFlips(n: Int, p: IntArray, pp: IntArray): Int {
    var flips = 1
    var first = p[0]

    if (p[first] != 0) {
        for (i in 0 until n) pp[i] = p[i]

        do {
            flips++
            var lo = 1
            var hi = first - 1
            while (lo < hi) {
                val temp = pp[lo]
                pp[lo] = pp[hi]
                pp[hi] = temp
                lo++
                hi--
            }
            val temp = pp[first]
            pp[first] = first
            first = temp
        } while (pp[first] != 0)
    }

    return flips
}
